/*************************************************************************
	> File Name: 001.素数筛.c
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 一  8/23 16:54:51 2021
 ************************************************************************/

#include <stdio.h>

//算法思想：
//1.标记一个范围内的数字是否是合数，没有被标记的为素数
//2. 算法的空间复杂度为O(n), 时间复杂度为O(n * loglogn)
//3. 总体思想是：用素数标记掉不是素数的数字，如果 i 是素数，则2 * i，3 * i,...都不是素数（用素数枚举合数）

//求解100以内的素数
#define MAX_N 100
int prime[MAX_N + 5];

void init() {
    for (int i = 2; i <= MAX_N; i++) {
        if (prime[i]) continue;
        prime[++prime[0]] = i; //循环利用数组，prime[0]记录素数个数，将得到的素数按照顺序存放
        for (int j = i * i; j <= MAX_N; j += i) { //j从i * i开始，是为了减少标记次数，不然就会有更多的重复标记。枚举a的倍数，则 a * b （b >= a)
            prime[j] = 1;
        }
    }
}

int main() {
    init();
    for (int i = 1; i <= prime[0]; i++) {
        printf("%d\n", prime[i]);
    }

    return 0;
}
